图神经网络（CS224w）学习笔记4 Link Analysis: PageRank (Graph as Matrix)

2023-02-14 12:42| 来源: 网络整理| 查看: 265

文章目录本章主要内容：一、Graph as Matrix二、PageRank / the Google Algorithm2.1 Web as a Graph2.1.1 节点的重要性衡量节点重要性 2.2 PageRank: The “Flow” Model2.3 PageRank: Matrix Formulation2.4 Connection to Random Walk2.5 特征向量公式 Eigenvector Formulation2.6 PageRank总结三、PageRank: How to solve?3.1 power iteration method 幂迭代法3.2 power iteration示例：3.3 PageRank的问题及其解决方案3.3.1 spider trap解决方案： random jumps or teleports 3.2.2 dead end解决方案：random jumps or teleports 3.3 两者对比：3.4 整体解决方案：random teleport3.5 The Google Matrix G3.6 random teleports举例：3.7 PageRank结果示例3.8 PageRank求解部分总结：四、Random Walk with Restarts & Personalized PageRank4.1 举例：推荐问题（一个由user和item两种节点组成的bipartite graph）4.2 Bipartite User-Item Graph4.2.1 衡量节点相似性4.2.2 图上的相似性：Random Walks with Restarts4.2.3 Random Walks4.2.4 以 Q 作为示例4.2.5 对不同PageRank变体的总结4.3 总结五、Matrix Factorization and Node Embeddings5.1 回忆上一章讲到的embedding lookup的encoder5.2 将节点嵌入视作矩阵分解：5.3 矩阵分解问题5.4 矩阵分解问题：基于random walk定义的相似性5.5 通过矩阵分解和随机游走进行节点嵌入的限制六、本章总结

本章主要内容：将图视为矩阵（邻接矩阵）的形式，以线性代数的角度来学习PageRank、随机游走和图嵌入。PageRank是一种衡量网络中节点重要性的指标，主要思想是如果一个节点被很多重要节点指向，那么该节点也很重要。可以从flow model / 线性方程组、power iteration（矩阵视角）、web surfer随机游走三种角度来看PageRank。求解PageRank的方法：power iteration。在求解PageRank的过程中会遇到spider traps和dead ends的问题，可以通过random teleport解决。M / G 是随机游走的概率转移矩阵。Personalized PageRank和Random Walk with Restarts（可用于衡量图中节点间相似性，如应用于推荐问题）：主要区别在于teleport sets。节点嵌入问题可以视作矩阵分解问题。一、Graph as Matrix 本节课研究矩阵角度的图分析和学习。这里的矩阵就是指邻接矩阵。将图视为矩阵形式，可以通过随机游走的方式定义节点重要性（即PageRank），通过矩阵分解matrix factorization (MF)来获取节点嵌入，将其他节点嵌入（如node2vec）也视作MF。二、PageRank / the Google Algorithm

PageRank是谷歌搜索用的算法，用于对网页的重要性进行排序。在搜索引擎应用中，可以对网页重要性进行排序，从而辅助搜索引擎结果的网页排名。

2.1 Web as a Graph

如果将Web当作是一个图，其中Web中的网页作为图的节点，Web中的超链接作为图的边。有一些问题会影响我们如何定义节点（但是本节课暂时不考虑这些问题）： 4. Dynamic pages created on the fly2 5. dark matter：不可达（如有密码等）的database generated pages

一个网页之间互相链接的情况的示例：在早期的Web链接是导航的，今天很多链接都是事务性的(不是用来从一个页面跳转到另一个页面，而是用来发布、评论、喜欢、购买……) 本课程中主要仅考虑那种网页之间互相链接的情况。将网页看作有向图，以链接指向作为边的方向（这个网页/节点能直接跳转到的网页就作为其下一个节点successor）其他可表现为有向图形式的信息网络示例：论文引用，百科全书中词条间的互相引用。

2.1.1 节点的重要性

在图中，我们想要定义节点的重要性importance，通过网络图链接结构来为网页按重要性分级rank。以下将介绍3种用以计算图中节点重要性的方法：

网页排序 PageRank个性化的网页排序 Personalized PageRank (PPR)重新开始的随机游走 Random Walk with Restarts(RWR) 衡量节点重要性

认为一个节点的链接越多，那么这个节点越重要。有向图有入边（in-coming links）和出边（out-going links）两种情况。可以想象，入边比较不容易造假，比较靠谱，所以用入边（in-links）来衡量一个节点的重要性。可以认为一个网页链接到下一网页，相当于对该网页重要性投了票（vote）。所以我们认为一个节点的入边（in-links）越多，那么这个节点越重要。同时，我们认为来自更重要节点的边，在比较重要性时的权重vote更大。这就成了一个递归（recursive）的问题——要计算一个节点的重要性就要先计算其predecessors的重要性，计算这些predecessors的重要性又要先计算它们predecessors的重要性……

2.2 PageRank: The “Flow” Model

来自重要页面的“投票”更有价值:

链接权重与其source page的重要性成正比例如果网页 i i i的重要性是 r i r_i ri ，有 d i d_i di个out-links，那么每个边的权重就是 r i / d i r_i/d_i ri/di。网页 l l l的重要性 r j r_j rj是其in-links上权重的总和。从而得到对节点 j j j 的级别 r j r_j rj r的定义： r j = ∑ i → j r i d i r_j=\sum\limits_{i\rightarrow j}\frac{r_i}{d_i} rj=i→j∑diri （ d i d_i di 是节点 i i i 的出度）以这个1839年的网络为例：在直觉上我们好像可以用高斯消元法（Gaussian elimination）来解这个线性方程组，但此方法的算法时间复杂度为 O ( N 2 ) O\left( N^2 \right) O(N2)，也可以看出这种方法不好用。所以我们寻找更好用的矩阵形式解法。 2.3 PageRank: Matrix Formulation 建立随机邻接矩阵（stochastic adjacency matrix）M：网页 j j j有 d j d_j dj条出边，如果 j → i ， M i j = 1 d j j\rightarrow i，M_{ij}=\frac{1}{d_j} j→i，Mij=dj1 。M是列随机矩阵column stochastic matrix（列和为1）。M的第 j j j 列可以视 j j j在邻居节点上的概率分布。 rank vector r ⃗ \vec{r} r ：每个网页 i i i的重要性得分 r i r_i ri ∑ i r i = 1 \sum_i\mathbf{r}_i=1 ∑iri=1（所以 r r r也可被视为是网络中所有节点的概率分布）我们可以得到下面的等式（r是矩阵M的特征向量）（这里上式中 M M M的第 j j j行被指向的节点对应的列 i i i的元素就是 1 / d i 1/d_i 1/di ，该列对应的是 r i \mathbf{r}_i ri，下式求和相加就能得到上式）flow equation和矩阵对比的举例： 2.4 Connection to Random Walk 假想一个网上浏览器的随机游走过程，在 t 时间在网页 i i i上，在t+1时间从 i i i的out-links中随机选一条游走。如此重复过程。向量 p ( t ) \mathbf{p}(t) p(t)的第 i i i个坐标是 t 时间网上浏览器在网页 i i i的概率，因此向量 p ( t ) \mathbf{p}(t) p(t)是网页间的概率分布向量。平稳分布stationary distribution p ( t + 1 ) = M ⋅ p ( t ) p(t+1)=M⋅p(t) p(t+1)=M⋅p(t)（M是网上浏览器的转移概率，这个公式的推理感觉和 r = M ⋅ r \mathbf{r}=M\cdot \mathbf{r} r=M⋅r 其实类似）如果达到这种条件，即下一时刻的概率分布向量与上一时刻的相同： p ( t + 1 ) = M ⋅ p ( t ) = p ( t ) \mathbf{p}(t+1)=M\cdot \mathbf{p}(t)=\mathbf{p}(t) p(t+1)=M⋅p(t)=p(t)，则 p ( t ) \mathbf{p}(t) p(t)是随机游走的平稳分布(stationary distribution) r = M ⋅ r \mathbf{r}=M\cdot \mathbf{r} r=M⋅r，所以 r \mathbf{r} r也是随机游走的stationary distribution。这种做法将PageRank与随机游走概念进行了联合。 2.5 特征向量公式 Eigenvector Formulation 无向图的邻接矩阵的特征向量是节点特征eigenvector centrality，而PageRank定义在有向图的随机邻接矩阵上。1 * r \mathbf{r} r=M * r \mathbf{r} r rank vector r \mathbf{r} r 是随机邻接矩阵M的特征向量，对应特征值为1。从任一向量 u \mathbf{u} u 开始，极限 M ( M ( . . . M ( M u ) ) ) M(M(...M(M\mathbf{u}))) M(M(...M(Mu)))是网页浏览器的长期分布，也就是 r \mathbf{r} rr意思是无论怎么开局，最后结果都一样。这个感觉可以比较直觉地证明，PageRank=极限分布=M的principal eigenvector。根据这个思路，我们就能找到PageRank的求解方式：power iteration limit极限 limiting distribution极限分布相当于是random surfer一直随机游走，直至收敛，到达稳定状态。这个M的叠乘可以让人联想到Katz index叠乘邻接矩阵A。相比高斯消元法，power iteration是一种scalable的求解PageRank方法。 2.6 PageRank总结通过网络链接结构衡量图中节点的重要性。用随机邻接矩阵M建立web surfer随机游走模型。PageRank解方程 r = M ⋅ r \mathbf{r}=M\cdot \mathbf{r} r=M⋅r， r \mathbf{r} r可被视作M的principle eigenvector，也可被视作图中随机游走的stationary distribution。三、PageRank: How to solve?

对每个节点赋初始PageRank 迭代：重复计算每个节点的PageRank: r j t + 1 = ∑ i → j r i ( t ) d i r_j^{t+1}=\sum\limits_{i\rightarrow j}\frac{r_i^{(t)}}{d_i} rjt+1=i→j∑diri(t)（ d i d_i di是节点 i i i的出度）直至收敛 ( ∑ i ∣ r i t + 1 − r i t ∣ < ϵ ) (\sum_i|r_i^{t+1}-r_i^t|

【本文地址】

公司简介

联系我们